package str;

/**
 * @author : Rookie
 * @description : 字符串匹配
 * @date : 2023/8/21
 */
public class StringMatch {

    public static void main(String[] args) {
        String s = "abaabaabeca";
        String t = "abaabe";
        System.out.println(violentSolute(s,t));
        System.out.println(kmpMatch(s,t));
    }

    private static int violentSolute(String s,String t) {
        int i = 0,j=0,result=-1;
        boolean match = false;
        while (i<s.length() && j<t.length()) {
                if (s.charAt(i) == t.charAt(j)) {
                    i++;
                    j++;
                    if (j == t.length()) {
                        match = true;
                        break;
                    }
                } else {
                    i = i - j + 1;
                    j = 0;
                }
        }
        if (match) {
            result = i-t.length();
        }
        return result;
    }

    private static int kmpMatch(String s,String t) {
        int i = 0,j=0,result=-1;
        int[] next = getNext(t);

        StringBuilder sb = new StringBuilder();
        sb.append("j的值依次是：");
        while (i<s.length()) {
            sb.append(j).append(",");
            if (j==-1||s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                j=next[j];
            }
        }
        System.out.println(sb);
        if (j==t.length()) {
            result=i-j;
        }
        return result;
    }

    /**
     * 求next数组 next数组表示字符串前i-1个元素的最长相等前缀长度
     * @param t
     * @return
     */
    private static int[] getNext(String t) {
        int[] next = new int[t.length()];
        int j=0,k=-1;
        next[0]=-1;
        // 因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
        // 所以最后一次经过while循环时j为t.length-2
        while (j<t.length()-1) {
            //对应字符匹配情况下，s与t指向同步后移
            if (k==-1 || t.charAt(j) == t.charAt(k)) {
                j++;
                k++;
                next[j]=k;
            } else {
                k=next[k];
            }
        }
        return next;
    }

}
